class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = nums[0]
        for i in range(2, n + 1):
            dp[i] = max(dp[i - 1], dp[i-2] + nums[i-1]) 
        return dp[n]
    
'''
dp[i] = max(dp[i - 1], dp[i-2] + nums[i-1]) 
表示第i家时偷到的最多的钱。
dp[i - 1]表示i-1家要偷，
dp[i-2]表示i-1家不偷，这样就是i-2家偷到的最多的钱dp[i-2]和第i家偷到钱的总和，两者取最大值迭代。
'''